package sorting;

public class MergeSort {
	public int[] mergeSort(int[] array) {

		if (array.length == 1){
			return array;
		} else {
			int[] A = mergeSort(divide(array, true));
			int[] B = mergeSort(divide(array, false));
			int[] resultado = intercala(A, B);
			return resultado;
		}
	}

	private int[] intercala (int[] array1, int[] array2 ){
		int contadorArray1 = 0;
		int contadorArray2 = 0;
		int contadorArray = 0;
		int tamanhoDoArray = array1.length + array2.length;

		int[] arrayResultado = new int[tamanhoDoArray];


		while ( contadorArray1 < array1.length && contadorArray2 < array2.length ){

			if (array1[contadorArray1] < array2[contadorArray2]) {
				arrayResultado[contadorArray] = array1[contadorArray1];
				contadorArray1 ++;
			} else {
				arrayResultado[contadorArray] = array2[contadorArray2];
				contadorArray2 ++;
			}

			contadorArray ++;

		}

		if (contadorArray1 != array1.length ) {
			for ( int i = contadorArray1; i < array1.length; i++){
				arrayResultado[contadorArray] = array1[i];
				contadorArray ++;
			}
		}

		if (contadorArray2 != array2.length ) {
			for ( int i = contadorArray2; i < array2.length; i++){
				arrayResultado[contadorArray] = array2[i];
				contadorArray ++;
			}
		}

		return arrayResultado;
	}
	
	private int[] divide(int[] array, boolean ehComeco){
		int[] cabeca;
		int[] calda;


		if (array.length%2 == 0){
			cabeca = new int[array.length/2];
			calda = new int[array.length/2];

		} else {
			cabeca = new int[(array.length+1)/2];
			calda = new int[array.length/2];
		}

		int cont1 = 0;
		int cont2 = 0;
		for (int i = 0; i < array.length; i++){
			if (i < cabeca.length ){
				cabeca[cont1] = array[i];
				cont1 ++;
			} else {
				calda[cont2] = array[i];
				cont2 ++;
			}			
		}

		if (ehComeco) {
			return cabeca;
		}

		return calda;
	}


}